package com.rui.study.algorithm.SORT_6_堆排序;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2018-11-26 11:38
 **/
public class HeapSort {

    public static void sort(int[] a) {
        /* 1.构建堆 */
        int n = a.length - 1;
        buildHeap(a, n);

        int s = n;  // 堆的大小
        while (s>0) {
            /* 2.交换堆顶元素 */
            swap(a, 0, s);
            s--;
            /* 3.堆大小减一，堆化 */
            heapify(a, s, 0);
        }
    }

    /**
     * 构建堆
     * @param a
     * @param n
     */
    private static void buildHeap(int[] a, int n) {
        // 从下往上构建堆
        for (int i = (n-1)/2; i>=0; i--) {
            heapify(a, n, i);
        }
    }

    /**
     * 堆化
     * @param a
     * @param n
     * @param i
     */
    private static void heapify(int[] a, int n, int i) {
        while (true) {
            int maxpos = i;
            int l = 2*i+1;
            if (l <= n && a[i] < a[l])
                maxpos = l;
            int r = 2*i+2;
            if (r <= n && a[maxpos] < a[r])
                maxpos = r;
            if (maxpos == i)
                break;
            swap(a, i, maxpos);
            i = maxpos;
        }
    }

    /**
     * 交换
     * @param a
     * @param i
     * @param j
     */
    private static void swap(int[] a, int i, int j) {
        a[i] += a[j];
        a[j] = a[i] - a[j];
        a[i] = a[i] - a[j];
    }
}
